The present invention relates to image analysis and, more particularly, but not exclusively to pattern matching using projection kernels in order to achieve real time results.
Many applications in Image Processing and Computer Vision require finding a particular pattern in an image. This task is referred to as Pattern Matching and may appear in various forms. Some applications require detection of a set of patterns in a single image, for instance, when a pattern appears under various transformations, or when several distinct patterns are sought in the image. Other applications require finding a particular pattern in several images. The pattern is typically a 2D image fragment which is much smaller than the image. In video applications, a pattern may also take the form of a 3D spatio-temporal fragment, representing a collection of 2D patterns over a succession of frames.
Finding a given pattern in an image is typically performed by scanning the entire image, and evaluating the similarity between the pattern and a local 2D window about each pixel. In video pattern matching, the similarity is calculated for each pixel in the 3D spatio-temporal stack, where the distance is calculated between two 3D data cubes. Reference is herein made to FIG. 3 below which shows pattern matching in 2D and in 3D: For each pixel location, a local neighborhood is compared with the given pattern.
There are various measures of similarity that may be used in this scheme and it is arguable as to which measure is preferable (see references [19, 17, 21, 2] as listed at the end of the background for reviews and discussions). One of the more common approaches is to assume that the similarity measure is a norm distance, specifically, the Euclidean distance. Given two images I1(x; y) and I2(x; y), the Euclidean distance between them is evaluated by:
            d      E        ⁡          (                        I          1                ,                  I          2                    )        =                                                I            1                    ⁡                      (                          x              ,              y                        )                          -                              I            2                    ⁡                      (                          x              ,              y                        )                                      =                  (                              ∑                          x              ,              y                                ⁢                                          ⁢                                    [                                                                    I                    1                                    ⁡                                      (                                          x                      ,                      y                                        )                                                  -                                                      I                    2                                    ⁡                                      (                                          x                      ,                      y                                        )                                                              ]                        2                          )            
There is a strong argument against the Euclidean distance as an image similarity metric in that it does not take into account the 2D topology of an image and it is not in accord with human perception [10, 8, 18, 24]. However there is an advantage in using this measure since it allows the naive calculations to be greatly reduced by introducing a convolution scheme. This significantly reduces complexity and runtime. Another reason for the popularity of the Euclidean distance is the ability to reduce the representation of linear spaces using Principle Component Analysis (PCA) approaches These approaches are helpful when a set of patterns are sought in an image. Using PCA in such cases, it is possible to efficiently represent the pattern space using a small number of pattern basis vectors, so that the complexity of the search process can be reduced significantly (see e.g. [3]). In the embodiments described hereinbelow we deal with Euclidean distance, however, the general scheme is applicable to any distance measure that forms a norm. The Euclidean distance is merely a particular case thereof